CODE 103. Substring with Concatenation of All Words

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/11/03/2013-11-03-CODE 103 Substring with Concatenation of All Words/

访问原文「CODE 103. Substring with Concatenation of All Words」

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening
characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).

public ArrayList<Integer> findSubstring(String S, String[] L) {
	// IMPORTANT: Please reset any member data you declared, as
	// the same Solution instance will be reused for each test case.
	Map<String, Integer> wordMap = new HashMap<String, Integer>();
	ArrayList<Integer> starts = new ArrayList<Integer>();
	int wordLength = L[0].length();
	int wordNumber = L.length;
	int allLength = wordLength * wordNumber;
	for (String l : L) {
		if (wordMap.containsKey(l)) {
			int num = wordMap.get(l);
			wordMap.put(l, num + 1);
		} else {
			wordMap.put(l, 1);
		}
	}
	for (int i = 0; i <= S.length() - allLength; i++) {
		Map<String, Integer> tmpWordMap = new HashMap<String, Integer>();
		boolean flag = true;
		for (int k = i, curWordNum = 0; curWordNum < wordNumber; k += wordLength, curWordNum++) {
			String tmpStr = S.substring(k, k + wordLength);
			if (tmpWordMap.containsKey(tmpStr)) {
				int number = tmpWordMap.get(tmpStr);
				tmpWordMap.put(tmpStr, number + 1);
			} else {
				tmpWordMap.put(tmpStr, 1);
			}
			if (!wordMap.containsKey(tmpStr)
					|| tmpWordMap.get(tmpStr) > wordMap.get(tmpStr)) {
				flag = false;
				break;
			}
		}
		if (flag) {
			starts.add(i);
		}
	}
	return starts;
}